nth root algorithm

The principal nth root $\sqrt[n]{A}$ of a positive real number A, is the positive real solution of the equation $x^n=A$. For a positive integer n there are n distinct complex solutions to this equation if $A>0$, but only one is positive and real.

Using Newton's method

Newton's method is a method for finding a zero of a function f(x). The general iteration scheme is:

1. Make an initial guess $x_0$
2. Set $x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$
3. Repeat step 2 until the desired precision is reached.

The n^th root problem can be viewed as searching for a zero of the function

$f(x)=x^n-A$

So the derivative is

$f^{\prime }(x)=n{x}^{n-1}$

and the iteration rule is

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

$=x_k-\frac{x_k^n-A}{n{x}_k^{n-1}}$

$=x_k+\frac{1}{n}[-x_k+\frac{A}{x_k^{n-1}}]$

$=\frac{1}{n}\left[(n-1)x_k+\frac{A}{x_k^{n-1}}\right].$

See also

• Recurrence relation
• Shifting nth root algorithm
• Halley's method
• Householder's method

References

• Atkinson, Kendall E. (1989), An introduction to numerical analysis (2nd ed.), New York: Wiley, ISBN 0-471-62489-6 .